# 剑指Offer题解 - Day50

# 剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [9,1,7,9,7,9,7]
输出：1

1
2

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

思路：

本题是昨天题解的升级版。可以先回归昨天的题解，再来看本题。

既然是升级版，那本题依旧需要采用位运算来求解。本题没有限制时间复杂度和空间复杂度，因此可以使用哈希表来存储元素出现的次数，然后返回出现一次的元素即可。

这里采用位运算来求解，哈希表的比较简单，作为思路扩展即可。

# 位运算

考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

那么现在的核心问题就是如何统计所有数字的各二进制位中 1 的出现次数。先来看最终代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let counts = Array.from({ length:32 }).fill(0); // 初始化32位数组
    for (let num of nums) {
        for (let i = 0; i < 32; i++) {
            counts[i] += num & 1; // 累加每一位二进制位
            num >>= 1;
        }
    }
    let res = 0; // 初始化结果
    let times = 3; // 初始化出现次数
    for (let i = 31; i >= 0; i--) {
        res <<= 1;
        res |= counts[i] % times;
    }
    return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度 O(n)。
空间复杂度 O(1)。

分析：

首先声明长度为 32 的数组。因为根据题目限制，数组元素的大小是 2^0 到 2^31 次方。我们用长度为 32 的数组来存放元素的每个二进制位之和。

然后进行数组元素的遍历。因为我们要逐位进行累加，因此内层遍历需要遍历 32 次。从最低位到最高位依次进行累加，累加的依据是当前元素和 1 的 与运算 的结果。但是每次和 1 进行与运算只能得知最低位是 1 还是 0 ，因此需要当前元素不断的右移，这样就可以确保当前元素的每一位都进行了累加。

然后初始化结果，和其他元素的出现次数。

累加的二进制每一位之和的时候，是通过右移操作，依次存放由低到高位的累加和。也就是说，counts[31]是最高位，counts[0]是最低位。此时需要逐个将二进制位恢复到结果当中。通过由高到低位的遍历，通过结果的不断左移，将counts数组中的二进制位信息恢复到res中。

需要注意的是，我们恢复二进制位到res时，需要将每一位进行和 3 取余操作。然后将res当前位 0 和取余操作进行 或运算 并赋值给res当前位。根据 或运算 的特点， 0 和任意值执行或运算，结果都等于任意值。因此通过取余并或运算将结果赋值给res ，就可以将只出现一次的数组从高位到低位恢复到res中。

最终返回res即可。

扩展：将times的值更改为变量m，就可以实现求数组中除一个数字出现一次外，其他数字都出现m次。核心原理就是，对所有数字的二进制位进行求和，并和m取模，最终剩下的二进制数就是只出现一次的数字。

复杂度方面，由于需要遍历数组，因此时间复杂度是O(n) ，额外声明的数组是 32 位，因此占用常数级别大小的空间。

# 状态机

本题还可以使用状态机来题解。该方法理解起来比较困难，但是效率比上述方法更高。

具体的方法可以参考Krahets给出的题解 (opens new window)。

# 总结

本题考查位运算的应用，统计并取模的方法具备普遍性，将代码中的 3 更改为任意值即可。

剑指Offer题解 - Day49 剑指Offer题解 - Day51